At the design stage in producing an object, it is necessary to represent a design condition as a function (objective function) of a design parameter, and to set (optimize) a design parameter so that the output value of the objective function (=objective function value) can be a desired value. In this case, the designer first determines a shape, then sets a range for the value of each design parameter and performs optimization in a design parameter space.
However, when there are a large number of design parameters, searching the entirety of the space incurs a combination explosion, and an optimizing calculation cannot be performed in real time.
Assume that SRAM (static random access memory) is designed as an example in producing an object.
A design target in designing SRAM is to guarantee both “allowance of operation stability against disturbance” and “allowance of write stability”. The performance of the former is called a static noise margin (hereinafter referred to as an SNM for short). The SNM is defined as the maximum value of the noise amplitude allowed for the operation of the SRAM. The larger the value of the SNM, the higher the stability. The performance of the latter is called a write margin (hereinafter referred to as a WM for short) and a hold noise margin (hereinafter referred to as an HNM for short). The larger the values of the WM and the HNM, the higher the stability.
The SNM and the WM or the WM and the HNM typically offset each other and then have a property wherein when one value is increased, the other value is decreased.
In designing the SRAM, the multi-objective optimization for simultaneously maximizing two physical amounts, that is, the SNM and the WM, or the three physical amounts, that is, the SNM, the WM, and the HNM, is required for the following design parameters of the SRAM.
<Design Parameters of SRAM>
                cell voltage        load gate length        driver gate length        transfer gate length        load width        driver width        transfer width        Wl (word line potential) control variable        Vth (amount of Vth change) of load        Vth (amount of Vth change) of driver        Vth (amount of Vth change) of transfer        
For example, in the case of the SNM and the WM, there is a general tendency to increase the yield of the SRAM, that is, to have larger values of the SNM and the WM, when larger sizes (of a gate length and width in the example above) represented by L1, L2, W1, W2, etc., and higher cell voltages and the like are obtained in an SRAM shape 801 illustrated in FIG. 8.
In this case, the optimization problem of maximizing the yield simultaneously for the SNM and the WM is the problem of simultaneously maximizing the objective function value representing the SNM and the objective function value representing the WM. That is, the simultaneous optimization problem of the yields corresponding to the SNM and the WM is to perform a calculation by the following equation to obtain the maximum value.Yield=min(objective function of SNM, objective function of WM)  equation (1)
The objective function of the SNM, the WM, etc. can typically be numerically-calculated by a simulator using a design parameter group configured by predetermined types of design parameters. Therefore, numerical calculations are performed by equation (1) above on the set of design parameters of a number of sets of samples, and a set of design parameter groups of simultaneously maximizing an obtained objective function value of the SNM and an obtained objective function value of the WM can be recognized, thereby attaining the-objective of the design.
However, the objective functions such as the SNM, the WM, etc. in the SRAM generally require complicated functional calculations performed by inputting design parameter groups configured by a number of types of design parameters. Therefore, when a numerical calculation using equation (1) is performed while changing the value of each design parameter between 0 and 1, outstanding computational complexity is required to calculate the optimum set of design parameters for simultaneously maximizing the objective function values, and it is significantly difficult to perform optimization in real time.
Under these circumstances, the following solution using a mathematical model expression of an objective function is known as a prior art for efficiently solving the above-mentioned multi-objective optimization problem in designs for producing an object such as SRAM.
First, a plurality of sets of samples of plural types of design parameter groups are prepared. It is not necessary to prepare a very large number of sets of samples.
Next, in a design simulator, a simulator calculation is performed on the plurality of sets of samples, and a numerical calculation is performed for the objective functions of the SNM and the objective function of the WM corresponding to each set of samples. Although two or three minutes are required to perform a numerical calculation of each objective function on a design parameter group of one sample, the calculating process is not a difficult process because there is not a very large number of set of samples.
Next, an approximating process by, for example, a method of least squares is performed on a plurality of sets of samples of pairs an objective function value of the SNM objective function value of the WM, and a design parameter group. As a result, each objective function model expression exemplified by the following equation is calculated after performing a mathematical approximation by a polynomial including each design parameter on the objective function of the SNM and the objective function of the WM.f1=−3.70880619227755703−1.815535443549214242e−2*x1+0.362756 928799239723e−1*x2+0.529879430721035828e−1*x3−0.18618740718 0227748e−1*x4+0.378882808207316458e−1*x5+0.5772189118800075 30e−2*x6+15.4475497344388622*x7+7.61316609791377275*x8+11.1 015094199909559*x9+11.1015094199909399*x10−1.84551068765900 172*x11  equation (2)
Generally, each objective function model expression of the SNM and the WM can be represented by the following equations. In the following equation, f1 and f2 are functions of a polynomial relating to, for example, design parameter x1, . . . , x11.objective function model expression of SNM=f1(x1, . . . , x11)objective function model expression of WM=f2(x1, . . . , x11).  equation (3)
In the prior art, each objective function model expression having practical approximation accuracy can be obtained using a smaller number of sets of samples of design parameter groups. In such a model expression, an objective function portion other than a sample value can be smoothly approximated only by selecting a sample value of a small number of design parameter groups, and an objective function model expression having a practically sufficient accuracy can be obtained.
Next, a logical expression obtained by adding a restriction condition and a quantifier (or a qualifier) on the design parameter included in the model equation to the calculated objective function model expression is generated.
For example, assume that, as an operation example 1, a designer requests the simultaneous maximum values for yields using the objective function model expressions f1 and f2 illustrated by equation (3).
In this case, the restriction condition is set as follows using equations (1) and (3) above.objective function model expression of SNM=f1(x1, . . . , x11)objective function model expression of WM=f2(x1, . . . , x11)yield=min(f1, f2)0≦xi≦1(i=1, 2, . . . , 11)
The above-mentioned restriction condition can be represented as a logical expression using the following equation.ex({x1,x2,x3,x4,x5,x6,x7,x8,x9,x10,x11}, (0≦x1≦1) and (0≦x2≦1) and (0≦x3≦1) and (0≦x4≦1) and (0≦x5≦1) and (0≦x6≦1) and (0≦x7≦1) and (0≦x8≦1) and (0≦x9≦1) and (0≦x10≦1) and (0≦x11≦1) and f1≧z and f2≧z);  equation (4)
In equation (4) above, ex indicates exists, and that an existence qualifier is added to the design parameter (=design variable) x1 through x11. That is, in equation (4) above, the following values are set.∃x1, ∃x2, ∃x3, ∃x4, ∃x5, ∃x6, ∃x7, ∃x8, ∃x9, ∃x10, ∃x11
In equation (4) above, each design parameter xi can be a value larger than 0 and smaller than 1. f1 and f2 in equation (4) are objective function model expressions equivalent to f1 and f2 in equation (3), and are represented as a polynomial of x1 through x11. z is a design variable indicating a yield.
For example, from the logical expression in equation (4) above, using the QE (quantifier elimination) method, which is well known due to its disclosure in the non-patent document “Introduction to Computational Algebraic and Geometry: Outline of CAD and QE (Mathematic Seminar, No. 11 2007 page 64-70 (by Hirokazu Anai and Kazuhiro Yokoyama))” and the non-patent document “Partial Cylindrical Algebraic Decomposition for Quantifier Elimination” by George E. Collins and Hoon Hong, Journal of Symbolic Computation, Volume 12, Number 3, 1991, pp. 299-328, the process of eliminating the design variable (=design parameter) x1 through x11 provided with qualifiers is performed. As a result, a logical expression indicating only the range of the design variable z can be obtained, and the designer can easily predict the maximum value of the design variable z.
Next, as an operation example 2 according to the prior art, it is assumed that a designer has requested the information of the relationship between a yield and a specific design parameter x1 using the objective function model expressions f1 and f2 described in equation (3).
In this case, the logical expression of the following equation is set.ex({x2, x3, x4, x5, x6, x7, x8, x9, x10, x11}, (0≦x1≦1) and (0≦x2≦1) and (0≦x3≦1) and (0≦x4≦1) and (0≦x5≦1) and (0≦x6≦1) and (0≦x7≦1) and (0≦x8≦1) and (0≦x9≦1) and (0≦x10≦1) and (0≦x11≦1) and f1≧z and f2≧z).  equation (5)
In this equation, a qualifier is set in all design parameters except x1.
In this case, the process of eliminating the design variables (=design parameters) x2 through x11 provided with qualifiers is performed by using the QE method from the logical expression of equation (5) above. As a result, a logical expression configured by just the design parameter x1 and the design variable z indicating a yield can be obtained.
As described above, after obtaining the logical expression including only the specific design variable (design parameter), for example in the case of the operation example 2 above, a design parameter remaining in the obtained logical expression, for example a sample point group (0≦x1≦1) relating to x1, is generated. Then, by calculating the logical expression above for each sample point, a possible value for the design variable z, that is, a possible area of the design variable z, is calculated. From the above-mentioned sample point and the corresponding value of z, a plot is generated on the 2-dimensional coordinates using x1 and z as axes, thereby drawing the possible area of z on the display or the like.
Thus, the designer can easily predict the relationship between the design parameter x1 and the design variable z corresponding to the yield.
As a practical calculating method for eliminating a design variable (=design parameter) provided with a qualifier in a logical expression by the QE method, a method called a CAD (Cylindrical Algebraic Decomposition) described in the non-patent document “Partial Cylindrical Algebraic Decomposition for Quantifier Elimination”, by George E. Collins and Hoon Hong, Journal of Symbolic Computation, Volume 12, Number 3, 1991, pp. 299-328 is well known.
The logical expression of a multi-objective optimization problem relating to the above-mentioned SNM and WM. is generalized by the following equation as described below.ex({x1, . . . , xt}, (0≦x1≦1) and . . . and (0≦xt≦1) and (0≦xt+1≦1) and . . . and (0≦xk≦1) and f1≧z and f2≧z);objective function model expression of SNM=f1(x1, . . . , xt,xt+1, . . . , xk)objective function model expression of WM=f2(x1, . . . , xt,xt+1, . . . , xk).  equation (6)
In the logical expression, a qualifier is provided for the design parameters x1 through xt, and no qualifier is provided for xt+1 through xk.
The multi-objective optimization problem under the above-mentioned assumption is to calculate the logical expression including only the design parameters xt+1 through xk without a qualifier by eliminating the design parameters x1 through xt provided with a qualifier from the input logical expression and the design variable z indicating the yield, and to obtain a set of design parameters xt+1 through xk without a qualifier that simultaneously maximize the design variable z using the logical expression. Assume that the design parameters x1 through xt with a qualifier have been eliminated using the QE/CAD method from the input logical expression. Then, as illustrated in FIG. 9, one of the design parameters xt+1 through xk is set as an axis of abscissas, and the design variable z is set as an axis of ordinates. With these settings, some polynomial curves relating to an objective function are obtained by projecting the objective functions f1 and f2 on the coordinate plane of FIG. 9. In the curves, the designer can recognize that selecting the set of the values of the design parameters xt+1 through xk corresponding to the point indicated by the arrow in FIG. 9 providing the maximum value of z while selecting the curve having the minimum value for z for each design parameter value is the optimum solution. The optimum solution indicates that the SNM and the WM can be simultaneously maximized in the accuracy range of the yield requested as the design specification when a set of values of the corresponding design parameters xt+1 through xk are selected. In FIG. 9, the blackened portion indicates an area which is inferior in yield to the optimum solution, but can which be selected as a set of the values of the design parameters xt+1 through xk. The area is called a possible area. On the other hand, the area not blackened above the possible area cannot be selected as a set of the values of the design parameters xt+1 through xk.
In this case, in the QE/CAD method, the following process is performed.
First, the design variable space indicated by the input logical expression configured by the design variable z and the design parameters xt+1 through xk without a qualifier is divided into a constant code area (called a “cell”) with respect to f1-z, f2-z. As viewed on the 2-dimensional plane configured by a design parameter without a qualifier and the design variable z indicating a yield, for example, each area (cell) indicated by a 0 (circle) in FIG. 10 is a constant code area with respect to f1-z, f2-z. The range of the divided cell is represented by a logical expression including an inequality using one or more of the design parameters xt+1 through xk and the design variable z. In one cell, a constant code of each objective function model expression is guaranteed for any set of each value of the design parameters xt+1 through xk and the value of the design variable z within the range. These cell divisions are performed on all combinations of sets of the design parameters xt+1 through xk without a qualifier and the design variable z. The total number of divided cells is approximately the number obtained by sequentially multiplying each design parameter by each corresponding number of divisions.
Next, for each cell divided as described above, the design parameters xt+1 through xk representing the cell and the value of the design variable z (called a “sample point”) are determined. These values are substituted for equation (6), including the design parameters x1 through xt provided with a qualifier, thereby determining whether or not the sample point satisfies equation (6). If equation (6) is satisfied, a logical expression using one or more of the design parameters xt+1 through xk without a qualifier and the design variable z which correspond to the cell is stored.
The logical expression obtained by combining the stored logical expressions after performing the above-mentioned determining process on all cells is calculated as a logical expression equivalent to the input logical expression and including only the design parameters xt+1 through xk without a qualifier and the design variable z.